\chapter{Grundlagen \label{grundlagen}}
Die Basis dieser Arbeit bildet das in diesem Kapitel beschriebene Volumenrendering-Framework. Abschnitt \ref{volumengrafik} gibt einen Einblick in das zugrunde liegende theoretische Konzept und erklärt die Notwendigkeit der Rekonstruktion.
\section{Das Volumenrendering-Framework}
\subsection{OpenGL \index{OpenGL}}
Die Grafikbibliothek \textit{OpenGL} ist die Grundlage vieler Grafikanwendungen und stellt die nötige Funktionalität für das Rendering bereit.\\
Innerhalb einer sogenannten \textit{Renderingpipeline} \index{Renderingpipeline} werden verschiedenste Berechnungen, beispielsweise zur gegenseitigen Verdeckung von Objekten, Belichtung oder Texturierung, durchgeführt. Zum Ende des Renderingprozesses wird die entstandene virtuelle Welt in eine zweidimensionale Ebene projiziert, die der Sicht auf die Welt entspricht. Das resultierende zweidimensionale Bild kann anschließend dargestellt werden. \cite{cg} \\
%Abbildung \ref{pipeline} zeigt die einzelnen Stufen der Renderingpipeline. \cite{cg} 
%\begin{figure}
%\centering
%\includegraphics[scale=0.5]{img/renderingpipeline.pdf}
%\caption[Quelle: \protect\cite{cg} Kapitel 2, Folie 7]{Der Renderingprozess von OpenGL}
%\label{pipeline}
%\end{figure}\\
OpenGL ermöglicht es seit Version 2.0, den starren Ablauf der Pipeline durch die Programmierung der Shader zu beeinflussen. Dazu stellt OpenGL eigens eine spezielle Hochsprache, die OpenGL Shading Language, bereit. \\ Das Wort \textit{Shader}\index{Shader} ist mit mehreren Bedeutungen belegt. Zum einen bezeichnet es eine Recheneinheit auf der Grafikkarte und zum anderen die Programme, die darauf laufen, sowie den Quelltext dieser Programme. \cite[Seite 35ff]{orange}
\subsection{OpenGL Shading Language\index{OpenGL Shading Language} \index{GLSL|see{OpenGL Shading Language}}}
Die \textit{OpenGL Shading Language} - oder kurz \textit{GLSL} - wurde entwickelt, um die vorherrschende Vielfalt an hardwarespezifischen low-level Shadersprachen durch eine allgemeine und verständlichere Hochsprache zu ersetzen. Daher bildet die Syntax der weit verbreiteten Programmiersprache C die Grundlage. Sie wurde teilweise eingeschränkt, aber auch durch einige Features aus C++ erweitert. \\ Auf der einen Seite werden beispielsweise grundsätzlich keine Pointer verwendet und es wird das call-by-value Paradigma angewendet. Auf der anderen Seite bietet es dafür Komfortfunktionen aus C++, wie etwa Variablendeklarationen an beliebiger Stelle. Zusätzlich sind die in der Grafik häufig gebrauchten Vektoren und Matrizen bis zur vierten Dimension Grundbestandteil der Sprache GLSL. Die zugehörigen Operatoren und die meisten Standardfunktionen rechnen mit Vektoren komponentenweise.\\ Beispielsweise existieren von der Standardfunktion des Sinus für Skalare auch überladene Funktionen für Vektoren. So berechnet \lstinline|sin(x)| den Sinus eines \lstinline|float x| und gibt einen \lstinline|float| zurück, während für einen vierdimensionalen Vektor \lstinline|vec4 v| der Sinus in allen vier Komponenten von \lstinline|v| einzeln ausgewertet wird und die Rückgabe ein \lstinline|vec4| ist. \\ Operatoren verhalten sich angewandt auf Vektoren ähnlich: Der Ausdruck \lstinline|v * v| bildet das komponentenweise Quadrat von \lstinline|v|, der Ausdruck \lstinline|v - 2| subtrahiert von jeder Komponente von \lstinline|v| den Wert \lstinline|2| et cetera. \\ Zugriff auf die einzelnen Komponenten eines Vektors erhält man durch die Arraynotation \lstinline|v[i]| mit \lstinline|int i| zwischen \lstinline|0| und \lstinline|3| oder durch Anhängen der Suffixe \lstinline|r, g, b, a| (als Farbkomponenten aufgefasst) beziehungsweise \lstinline|x, y, z, w|. \\ Eine ausführliche Beschreibung von GLSL findet sich in \cite[Kapitel 2 bis 5]{orange}. 
\subsection{Voreen \index{Voreen}}
Die \textit{Vo}lume \textit{Re}ndering \textit{En}gine ist ein Programm zur Visualisierung von Volumen und wird von der Arbeitsgruppe "`Visualisierung und Computergrafik"' am Institut für Informatik der Westfälischen Wilhelms Universität in Münster entwickelt.
\begin{figure}[h]
\centering
\includegraphics[scale=0.8]{img/voreenNetzwerk.png}
\caption{Ein Netzwerkgraph aus Prozessoren von Voreen}
\label{voreen}
\end{figure} \\
Das Prinzip bei Voreen ist modular. Sogenannte \textit{Prozessoren} \index{Prozessor} können verschiedene Funktionen übernehmen und werden in einem \textit{Netzwerkgraphen}\index{Netzwerkgraph} - wie in Abbildung \ref{voreen} zu sehen - durch \textit{Ports}\index{Port} miteinander Verbunden. Die Pfeile geben dabei den Datenfluss zwischen den Ports an. Ein Prozessor kann unter Anderem die Rolle eines Volumens (VolumeSource), eines Renderers (SingleVolumeRaycaster), oder der Ausgabe (Canvas) übernehmen. Fast jeder Prozessor bietet mehrere, teils komplexe Einstellungsmöglichkeiten (Properties), die das Rendering beeinflussen - etwa Belichtung oder Transferfunktionen. \\ Wesentliche Teile des Programms, wie der für diese Arbeit modifizierte "`SingleVolumeRaycaster"', der das in Abschnitt \ref{raycasting} beschriebene Raycasting umsetzt, sind ob des massiven Umfangs der Berechnungen als GLSL-Shader implementiert und laufen auf der Grafikkarte. Die in Kapitel \ref{implementierung} aufgeführten Implementierungen der verschiedenen Filter sind daher durch eine \lstinline|#include|-Anweisung leicht in den entsprechenden Shader einzubinden und können den Standard-Hardwarefilter ersetzen.
\section{Volumengrafik \label{volumengrafik}}
Das Volumenrendering ist zwar eine dreidimensionale Visualisierung und nutzt für die Berechnungen heutzutage auch die Grafikkarte in hohem Maße, dennoch unterscheidet es sich stark von traditioneller 3D-Grafik.
Traditionelle Grafikmethoden nutzen 3D-Gittermodelle - das heißt Netze aus Polygonen - um die Oberfläche von Objekten zu beschreiben. Das Ergebnis des Renderings ist ein Bild, in dem die Oberflächen der beschriebenen Objekte zu sehen sind. \\
Die \textit{Volumengrafik} \index{Volumengrafik} verfolgt dagegen den Ansatz komplette Objekte durch eine Punktwolke zu repräsentieren, wodurch auch das Innere der Objekte dargestellt werden kann. Insbesondere in der Medizin hat diese Art der Visualisierung ein wichtiges Anwendungsgebiet, da zum Beispiel Computertomographen und Magnetresonanztomographen "`nur"' ein dreidimensionales Array mit Messwerten liefern. Aufgabe des Volumenrenderings ist es, diese Daten sichtbar zu machen.\\
Andere Anwendungsgebiete finden sich beispielsweise im Bereich der Visualisierung seismischer Messungen, der numerischen Strömungsmechanik oder in Computerspielen respektive Simulationen zur realistischen Darstellung von Wolken, Flüssigkeiten, Feuer et cetera. \cite[Seite xi]{real} \\
\\
Generell lässt sich Volumengrafik überall dort einsetzen, wo eine dreidimensionale Abbildung $g : \mathbb{R}^3 \to \mathbb{R}^n$ visualisiert werden soll. Typischerweise ist $n=1$ und $g$ dabei nicht als kontinuierliche Funktion gegeben, sondern liegt in Form von endlich vielen Funktions\-werten, den sogenannten \textit{Samples} \index{Sample} vor. Im Bereich der Volumengrafik werden diese Samples auch \textit{Voxel} genannt. \index{Voxel} Sie werden entweder durch die Auswertung einer kontinuierlichen Funktion oder analoger Signale an den Samplepositionen bestimmt, oder liegen durch die Art und Weise des Messverfahrens - wie etwa der Computertomographie - bereits in der Form diskreter Messpunkte vor. Vereinfachend nimmt man dabei an, dass alle Samples äquidistant im Einheitswürfel liegen (reguläres Gitter) und eine feste Anzahl von Samples gegeben ist, etwa $41 \times 41 \times 41$. \cite[Seite 3]{real} 
\subsection{Raycasting \label{raycasting} \index{Raycasting}}
Neben dem Slicing \cite[Kapitel 3.2]{real} und anderen Methoden, ist das sogenannte \textit{Raycasting} (Abbildung \ref{raycastingSchema}) nur eine Möglichkeit des Volumenrenderings.  \cite[Seite 165ff]{real}
\begin{figure}[!b]
\centering
\includegraphics[scale=1]{img/raycasting.pdf}
\caption{Schema des Raycasting}
\label{raycastingSchema}
\end{figure}
Hierbei bildet eine virtuelle Bildfläche, die zwischen dem virtuellen Betrachter und dem Volumen platziert wird, die Grundlage. Für jedes Pixel der Bildfläche wird mittels der Beobachter\-po\-si\-tion und der jeweiligen Pixelposition eine Gerade aufgespannt. Die Geraden stellen dabei (Licht-)Strahlen dar, die in umgekehrter Richtung - das heißt vom Beobachter ausgehend - das Volumen durchlaufen (\textit{traversieren}). \index{Traversierung} Jeder Strahl wird bei der Traversierung an diskreten Positionen (rot) \textit{gesampelt}, \index{Sampling} das heißt, es wird anhand der aktuellen Position der zugehörige Wert berechnet (siehe Rekonstruktion in Kapitel \ref{rekonstruktion}). Eine sogenannte \textit{Transferfunktion} \index{Transferfunktion} ordnet diesem Wert eine Farbe $C_{src}$ und einen \textit{Alphawert} $\alpha_{src}$ (Undurchsichtigkeit) \index{Alphakanal} zu. Mit dem Kompositionsschema \begin{eqnarray*}
C_{dst} &= C_{dst} + (1 - \alpha_{dst}) C_{src} \\ \alpha_{dst} &= \alpha_{dst} + (1 - \alpha_{dst}) \alpha_{src}
\end{eqnarray*} werden der endgültige Farbwert $C_{dst}$ und der endgültige Alphawert $\alpha_{dst}$ durch sukzessives Akkumulieren der Farbwerte an den Samplepositionen ermittelt. \\
Als eine Optimierung bricht die \textit{Early Ray Termination} \index{Early Ray Termination} dabei unnötige Traversierung der Strahlen ab, wenn alle folgenden Farbwerte $C_{src}$ kaum noch zur Endfarbe $C_{dst}$ beitragen. Das ist dann der Fall, wenn der Alphakanal $\alpha_{dst}$ einen gewissen Schwellenwert (typischerweise $\alpha = 0.95$) überschreitet und alle nachfolgenden Samples bereits weitgehend überdeckt sind. \cite[Seite 171]{real}\\
Liegt nach der Traversierung eines Strahls die Endfarbe vor, wird sie dem zugehörigen Pixel der Bildfläche zugeordnet. Alle Pixel der Bildfläche zusammengenommen ergeben das fertige Rendering.

\subsection{Konsequenz}
Die beispielhaft dargelegte Raycastingmethode des Volumenrenderings zeigt auf, dass es nötig wird, Werte, die zwischen den gegebenen Voxeln (schwarz) liegen, zu berechnen. Verläuft etwa ein Strahl zwischen den Voxeln hindurch, dann müssen an den Samplepositionen (rot) die Originalwerte rekonstruiert werden. \cite[Seite 21]{real} Genau dies ist die Aufgabe der Rekonstruktion beziehungsweise Interpolation, die die umgebenden Voxel zur Berechnung heranzieht. Das geschieht mithilfe einer Faltung (siehe Abschnitt \ref{faltung}) der Voxel mit speziellen Funktionen, den \textit{(Rekonstruktions-)Filtern}\index{Filter}. \cite[Seite 1]{filter}